Network Function Virtualization (NFV) is an emerging paradigm that turnshardware-dependent implementation of network functions (i.e., middleboxes) intosoftware modules running on virtualized platforms, for significant costreduction and ease of management. Such virtual network functions (VNFs)commonly constitute service chains, to provide network services that trafficflows need to go through. Efficient deployment of VNFs for network serviceprovisioning is key to realize the NFV goals. Existing efforts on VNF placementmostly deal with offline or one-time placement, ignoring the fundamental,dynamic deployment and scaling need of VNFs to handle practical time-varyingtraffic volumes. This work investigates dynamic placement of VNF service chainsacross geo-distributed datacenters to serve flows between dispersed source anddestination pairs, for operational cost minimization of the service chainprovider over the entire system span. An efficient online algorithm isproposed, which consists of two main components: (1) A regularization-basedapproach from online learning literature to convert the offline optimaldeployment problem into a sequence of one-shot regularized problems, each to beefficiently solved in one time slot; (2) An online dependent rounding scheme toderive feasible integer solutions from the optimal fractional solutions of theone-shot problems, and to guarantee a good competitive ratio of the onlinealgorithm over the entire time span. We verify our online algorithm with solidtheoretical analysis and trace-driven simulations under realistic settings.
展开▼
